﻿using System;
using System.Linq;
using Algoritmia.DataStructures.Lists;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Utils;

namespace Algoritmia.Problems.GeneralizedCoinChange.QuantityAndSizeModeling
{
    public class MemoizedDynamicCoinChanger : IDynamicCoinChanger
    {
        private readonly IList<int> _values;
        private readonly int _n;
        private readonly IList<double> _weights;
        private readonly Func<IMap<Tuple<int, int>, double>> _createMap;

        public MemoizedDynamicCoinChanger(IList<int> values, IList<double> weights = null,
            Func<IMap<Tuple<int,int>,double>> createMap = null)
        {
            _createMap = createMap ?? (() => AlgoritmiaFactory.Maps<Tuple<int, int>, double>.Default);
            _values = values;
            _n = values.Count;
            _weights = weights ?? Enumerable.Repeat(1.0, _n).ToAlgoritmiaList();
        }

        #region Implementation of IDynamicCoinChanger

        public double Weight(int Q)
        {
            Func<int, int, double> L = null;
            var mem = _createMap();
            L = (q, n) =>
                    {
                        if (q == 0 && n == 0)
                        {
                            return 0;
                        }

                        if (q > 0 && n == 0)
                        {
                            return double.PositiveInfinity;
                        }

                        var upper = q/_values[n - 1];

                        for (int i = 0; i <= upper; i++)
                        {
                            var callTuple = new Tuple<int, int>(q - i*_values[n - 1], n - 1);
                            if (!mem.Contains(callTuple))
                            {
                                mem[callTuple] = L(callTuple.Item1, callTuple.Item2);
                            }
                        }
                        return
                            Enumerable.Range(0, upper + 1).Select(
                                i => mem[new Tuple<int, int>(q - i*_values[n - 1], n - 1)] + i*_weights[n-1]).Min();
                    };
            var callArgs = new Tuple<int, int>(Q, _n);
            mem[callArgs] = L(Q, _n);
            return mem[callArgs];
        }

        #endregion
    }
}
